Phạm Văn Xảo là người có nhiều mưu trí, theo giúp Lê Lợi tham gia khởi nghĩa Lam Sơn, được phong chức Khu mật đại sứ.[3]

Sử sách không ghi rõ ông tham gia khởi nghĩa Lam Sơn năm nào nhưng mãi tới năm 1426 ông mới xuất hiện lần đầu tiên.[4] Tháng 8 năm 1426, sau khi làm chủ từ Thanh Hoá đến Thuận Hoá, Lê Lợi chia quân cho các tướng làm 3 cánh bắc tiến. Phạm Văn Xảo, Đỗ Bí, Trịnh Khả, Lê Triện ra phía Tây bắc, Lưu Nhân Chú, Bùi Bị ra phía Đông bắc; Đinh Lễ, Nguyễn Xí ra đánh Đông Quan.

Tiến đến gần Đông Quan, Phạm Văn Xảo và các tướng nghe tin viện binh nhà Minh từ Vân Nam do Vương An Lão chỉ huy sắp tiến sang theo đường Hưng Hoá. Ông bèn cùng Lê Triện chia quân làm hai cánh: ông cùng Trịnh Khả tiến lên Tây bắc đánh chặn Vương An Lão, còn Lê Triện đóng đồn phía tây Ninh Giang uy hiếp Đông Quan.

Phạm Văn Xảo và Trịnh Khả tiến đến Tam Giang, lại chia quân làm thanh thế tiếp ứng cho nhau.[3] Đô ty Vân Nam là Vương An Lão mang hơn 1 vạn quân sang đánh, đến cầu Xa Lộc thuộc Tam Giang, bị hai tướng chặn đánh phá tan tành, chém hơn 1000 quân, quân Minh bị chết đuối rất nhiều.[2] An Lão thua trận bỏ chạy vào thành Tam Giang bấy giờ có quân Minh chiếm cứ.

Trong khi đó Đinh Lễ, Nguyễn Xí và Lý Triện cũng phá tan viện binh của Vương Thông ở Tốt Động. Lê Lợi tiến đại quân ra bắc vây hãm Đông Quan. (xem bài Lê Lợi)

Năm 1427, vua Minh lại cử viện binh sang. Cánh chủ lực do Liễu Thăng sang đường Lạng Sơn, cánh kia do Mộc Thạnh lại từ Vân Nam sang. Phạm Văn Xảo và Trịnh Khả tiến lên giữ ải Lê Hoa (Tuyên Quang) ở nơi hiểm yếu cố thủ không cho Mộc Thanh tiến sâu. Thạnh là viên tướng lão luyện, cốt chờ thắng bại của Liễu Thăng mới quyết định hành động. Phạm Văn Xảo cũng án binh không đánh.[2]

Sau khi chém được Liễu Thăng và tiêu diệt cánh quân chủ lực, Lê Lợi sai mang ấn tín của Thăng đến chỗ Thạnh. Thạnh sợ hãi bỏ chạy. Phạm Văn Xảo và Trịnh Khả thừa cơ tung quân ra đánh, phá địch ở Lãnh Cầu, Đan Xá, chém hơn 1 vạn quân, bắt sống hơn 1000 người ngựa, thu được rất nhiều khí giới.